package com.kingwood.algorithm.test;

import java.util.PriorityQueue;
import java.util.StringJoiner;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/3/26 13:24
 * @Modified By：
 * @Version 1.0
 */
public class HafumanTree2 {

    public static class TreeNode {
        public int weight;
        public int height;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(TreeNode left, TreeNode right, int weight, int height) {
            this.left = left;
            this.right = right;
            this.weight = weight;
            this.height = height;
        }
    }

    public static TreeNode createHafumanTree(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        int len = arr.length;
        PriorityQueue<TreeNode> pq = new PriorityQueue<>((a, b) -> a.weight != b.weight ? a.weight - b.weight : a.height - b.height);
        for (int i = 0; i < len; i++) {
            pq.add(new TreeNode(null, null, arr[i], 0));
        }

        while (pq.size() > 1) {
            TreeNode left = pq.poll();
            TreeNode right = pq.poll();

            pq.offer(new TreeNode(left, right, left.weight + right.weight, right.height + 1));
        }

        return pq.peek();
    }

    public static void midOrder(TreeNode root, StringJoiner sj) {
        if (root == null) {
            return;
        }

        if (root.left != null) {
            midOrder(root.left, sj);
        }

        sj.add(root.weight + " ");

        if (root.right != null) {
            midOrder(root.right, sj);
        }
    }

    public static void main(String[] args) {
        StringJoiner sj = new StringJoiner(" ");
        int[] arr = {5, 15, 40, 30, 10};
        TreeNode root = createHafumanTree(arr);
        midOrder(root, sj);
        System.out.println(sj.toString());
    }
}
